1. Field of the Invention
The present invention generally relates to a device and a method for variable length decoding and, more particularly, to a device and a method for variable length decoding used in a high compression-ratio video system for shortening the critical path.
2. Description of the Prior Art
Variable Length Coding (VLC) is widely adopted in many compression systems, such as JPEG (Joint Photographic Experts Group) and MPEG (Moving Picture Experts Group). Accordingly, a variable length decoder (VLD) is also required in a compression system so as to decode the variable length coding. The VLD circuit was proposed early in 1991 to comprise registers, barrel shifters (BS) and a VLC table.
Please refer to FIG. 1, which is a circuit diagram showing a conventional VLD circuit. In FIG. 1, the VLD circuit 100 comprises 16-bit registers D1 101, D2 103, a barrel shifter 105, a VLD table 107, an adding device 109 and a register 111. The barrel shifter 105 receives 32-bit input data from the 16-bit registers D1 101, D2 103. The barrel shifter 105 selects from the 32-bit data by shifting the contents in the registers D1 101, D2 103 and outputs 16-bit data to the VLD table 107 for decoding.
More particularly, the VLD table 107 includes a code-word deciding unit 121 and a code-length output unit 122. When the VLD table 107 receives 16-bit data from the barrel shifter 105, the code-word deciding unit 121 determines the bits to be decoded. Accordingly, the code-length output unit 122 outputs the code-length in a 4-bit data to the adding device 109. The adding device 109 accumulates according to the code-length. In other words, the sum output by the adding device 109 is added to the output of the adding device 109 through the feedback path. The accumulated sum is also stored in the register 111. The output sum in a 4-bit data by the adding device 109 controls the shifting of the barrel shifter 105 so that the barrel shifter 105 selects 16-bit data from the 32-bit data. The carry (Cout) output from the adding device 109 controls the timing at which new 16-bit data is read from the register 103.
Therefore, when the 16-bit data is read from the register 103, the data is loaded from the register 103 into the register D1 101 and the register D2 103. The data loaded in the register D1 101 and the register D2 103 is then input into the barrel shifter 105. The barrel shifter 105 decodes according to the 16-bit data input to the VLD table 107. Then, the VLD table 107 decodes according to the 16-bit data and outputs the code-word and the code-length.
Please also refer to FIG. 2 and FIG. 3. FIG. 2 is an example of conventional VLC decoder operations that the barrel shifter 105 shifts its opening windows to the next code-word according to the accumulated code-length. FIG. 3 is an example of the VLC table 107. In FIG. 2, the barrel shifter 105 includes the 0th˜the 31st zones so as to store the input 32-bit data from the register D1 101 and the register D2 103. The undecoded bits appear at the output of the barrel shifter 105, as shown in each framed row from top to bottom in FIG. 2. At the beginning, the undecoded bits are 0111110000011101, which are determined by the code-word deciding unit 121 according to FIG. 3 that the 16th and 15th bits “01” correspond to “b” in FIG. 3, resulting in a code-length of 2. The accumulated shift is 2. Therefore, in the next decoding cycle, the barrel shifter 105 shifts 2 bits to the right and the undecoded bits are 1111000001110110. It is determined by the code-word deciding unit 121 that, according to FIG. 3, the 16th to 12th bits “11110” correspond to “g” in FIG. 3, resulting in a code-length of 5. The accumulated shift is 7.
Similarly, in the next decoding cycle, the barrel shifter 105 shifts 7 bits to the right and the undecoded bits are 0000111011001000. It is determined by the code-word deciding unit 121 that, according to FIG. 3, the 16th and 15th bits “00” correspond to “a” in FIG. 3, resulting in a code-length of 2. The accumulated shift is 9.
As the accumulated shift is as much as 15, the barrel shifter 105 shifts 15 bits to the right and the undecoded bits are 1100100011001010. It is determined by the code-word deciding unit 121 that, according to FIG. 3, the 16th and 14th bits “110” correspond to “e” in FIG. 3, resulting in a code-length of 3. The accumulated shift is 2 with a carry-out bit (Cout) of 1. Meanwhile, only the 0th bit “1” of the 32-bit data 01111100000111011001000110010101 from the register D1 101 and the register D2 103 is left undecoded. Therefore, the data in the register D2 103 is loaded into the register D1 102 and a new 16-bit word is loaded into the register D2 103, and the barrel shifter 105 shifts to the new position to prepare for the next decoding cycle.
Generally, when the VLD circuit 100 is used in low-level compression systems with code-length shorter than 16 bits, only one or two clock cycles are required for decoding, assuming that a clock cycle is 7.4 ns for 135 MHz specification. But if the VLD circuit 100 is used in high-level compression systems with code-length longer than 20 bits, the barrel shifter 105 decodes two 16-bit data loaded from the register D2 103. In other words, it takes two or three clock cycles to achieve decoding in high-level compression systems.
The critical path of the conventional VLD circuit 100 is:
the registers D1 101/D2 103→the barrel shifter 105→the VLC table 107→the adding device 109→the registers D1 101/D2 103,
which takes two or three clock cycles to achieve decoding and cannot be done in one 7.4-ns clock cycle for 135 MHz specification.
Therefore, there is need in providing a device and a method for variable length decoding so as to shorten the clock cycle for higher frequency systems.